class Solution {
public:
    int minDistance(string s1, string s2) {
        int n = s1.size(), m = s2.size();

        // 多加一个占位字符，方便填表
        s1 = " " + s1, s2 = " " + s2;

        // dp[i][j]表示s1的[0, i]个字符转换为s2前[0, j]个字符的最少操作数
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        // 初始化
        // dp[0][0]就是s1的[0, 0]个字符转换为s2前[0, 0]个字符的最少操作数，那就是0
        // dp[0][j]就是s1的[0, 0]个字符转换为s2前[0, j]个字符的最少操作数，那就是j，每次都插入一个字符
        // dp[i][0]就是s1的[0, i]个字符转换为s2前[0, 0]个字符的最少操作数，那就是j，每次都删除一个字符

        for(int i = 1; i <= n; i++)
            dp[i][0] = i;
        for(int j = 1; j <= m; j++)
            dp[0][j] = j;


        // 当末尾字符相同时，此时这个字符就可以舍弃了，因为都相等了，不正是我们想要的吗?
        // 末尾字符不相同时，此时就要进行三种操作
        // 1. 插入，在s1插入s2的末尾字符，之后，此时末尾字符就相同了，这个字符就可以舍弃了，看dp[i][j - 1]的情况了，此时我们进行了一次插入操作，所以就要+1
        // 2. 删除，删除s1的末尾字符，之后，去看s1的[0, i - 1]个字符和s2的[0, j]个字符是否相同，同理也要+1
        // 3. 替换，把s1的末尾字符替换为s2的末尾字符，此时就相当于末尾字符相同了，去看dp[i - 1][j - 1]，同理也要+1
        // 综上取上面三种情况的最小值再加1即可

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                // 末尾字符相同
                if(s1[i] == s2[j])
                    dp[i][j] = dp[i - 1][j - 1];
                // 末尾字符不相同，就有三种操作
                else
                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
            }
        }

        return dp[n][m];
    }
};